package ljl.alg.jianzhioffer.round2;

/**
 * 可以挨个数，不过还是在考察二分
 * 错位的那个数字右侧全都是错位的，挨个找即可
 *
 * 而且他说了只有一个数字是错位的
 *
 * 写了半天，超时了
 * 我真是不会二分法，真难！
 *
 * */
public class _53_2_missing_number {
    
    /**
    * 改了好几版，蒙对了
     * 1. r 改为 nums.length，因为啥呢？他说了，少一个数，其实应该是 nums.length + 1 个数
     * 2. l <= r 改为 l < r 不然就死循环了
     * 3. 直接返回 l
     *
     * 神奇的一逼，我不知道它为什么是对的？
     *
    * */
    public int missingNumber(int[] nums) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] != mid) r = mid;
            else l = mid + 1;
        }
        return l;
    }
    
    /**
     * 路飞说，退出循环时，i 指向右子数组首尾，j 指向左子数组末端
     * 返回 i 即可
     * */
    public int missingNumber2(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (nums[mid] == mid) i = mid + 1;
            else j = mid - 1;
        }
        return i;
    }
}
